// 包含标准输入输出库和内存管理库
#include <stdio.h>
#include <stdlib.h>  // 用于动态内存分配函数malloc和free

#define MaxSize 10   // 静态分配时的最大容量

// ========== 元素类型定义 ==========
// 使用typedef定义元素类型，方便以后修改数据类型
typedef int ElemType;   // 可以改为char、float、double等其他类型

// ========== 静态分配的顺序表 ==========
// 特点：内存大小在编译时就确定，不能改变
typedef struct {
    ElemType Data[MaxSize]; // 使用ElemType而不是直接用int
    int length;             // 当前实际长度
} StaticSqlList;

// ========== 动态分配的顺序表 ==========
// 特点：内存大小在运行时动态分配，可以根据需要调整
typedef struct {
    ElemType *Data;         // 指向动态分配内存的指针，存储ElemType类型
    int MaxSize;            // 最大容量（可以动态改变）
    int length;             // 当前实际长度
} DynamicSqlList;

// ========== 静态分配的函数 ==========

// 初始化静态顺序表
void InitStaticList(StaticSqlList *L) {
    printf("=== 初始化静态顺序表 ===\n");
    for (int i = 0; i < MaxSize; i++) {
        L->Data[i] = 0;     // 将所有位置初始化为0
    }
    L->length = 0;          // 长度设为0
    printf("静态顺序表初始化完成，固定容量：%d\n\n", MaxSize);
}

// 向静态顺序表插入元素
void InsertStaticList(StaticSqlList *L, int pos, ElemType value) {
    // 检查插入位置是否合法
    if (pos < 0 || pos > L->length) {
        printf("插入位置不合法！\n");
        return;
    }
    // 检查顺序表是否已满
    if (L->length >= MaxSize) {
        printf("静态顺序表已满，无法插入！\n");
        return;
    }
    
    // 将pos位置及之后的元素向后移动
    for (int i = L->length; i > pos; i--) {
        L->Data[i] = L->Data[i-1];
    }
    
    L->Data[pos] = value;   // 在pos位置插入新值
    L->length++;            // 长度加1
    printf("在静态表位置%d插入值%d成功\n", pos, value);
}

// ========== 动态分配的函数 ==========

// 初始化动态顺序表
void InitDynamicList(DynamicSqlList *L, int size) {
    printf("=== 初始化动态顺序表 ===\n");
    // 使用malloc动态分配内存，注意这里用sizeof(ElemType)
    L->Data = (ElemType*)malloc(size * sizeof(ElemType));
    
    // 检查内存分配是否成功
    if (L->Data == NULL) {
        printf("内存分配失败！\n");
        return;
    }
    
    // 初始化参数
    L->MaxSize = size;
    L->length = 0;
    
    // 初始化数组内容
    for (int i = 0; i < size; i++) {
        L->Data[i] = 0;
    }
    
    printf("动态顺序表初始化完成，初始容量：%d\n\n", size);
}

// 向动态顺序表插入元素
void InsertDynamicList(DynamicSqlList *L, int pos, ElemType value) {
    // 检查插入位置是否合法
    if (pos < 0 || pos > L->length) {
        printf("插入位置不合法！\n");
        return;
    }
    
    // 如果容量不够，动态扩展容量
    if (L->length >= L->MaxSize) {
        printf("容量不够，正在扩展动态顺序表...\n");
        
        int newSize = L->MaxSize * 2;  // 容量翻倍
        // 重新分配更大的内存空间，注意这里用sizeof(ElemType)
        ElemType *newData = (ElemType*)realloc(L->Data, newSize * sizeof(ElemType));
        
        if (newData == NULL) {
            printf("内存扩展失败！\n");
            return;
        }
        
        L->Data = newData;      // 更新指针
        L->MaxSize = newSize;   // 更新容量
        
        // 初始化新分配的空间
        for (int i = L->length; i < newSize; i++) {
            L->Data[i] = 0;
        }
        
        printf("容量扩展成功，新容量：%d\n", newSize);
    }
    
    // 将pos位置及之后的元素向后移动
    for (int i = L->length; i > pos; i--) {
        L->Data[i] = L->Data[i-1];
    }
    
    L->Data[pos] = value;   // 在pos位置插入新值
    L->length++;            // 长度加1
    printf("在动态表位置%d插入值%d成功\n", pos, value);
}

// 打印静态顺序表
void PrintStaticList(StaticSqlList *L) {
    printf("=== 静态顺序表内容 ===\n");
    printf("容量：%d（固定）, 当前长度：%d\n", MaxSize, L->length);
    printf("数据：");
    for (int i = 0; i < L->length; i++) {
        printf("%d ", L->Data[i]);  // 这里的打印格式要根据ElemType调整
    }
    printf("\n\n");
}

// 打印动态顺序表
void PrintDynamicList(DynamicSqlList *L) {
    printf("=== 动态顺序表内容 ===\n");
    printf("容量：%d（可变）, 当前长度：%d\n", L->MaxSize, L->length);
    printf("数据：");
    for (int i = 0; i < L->length; i++) {
        printf("%d ", L->Data[i]);  // 这里的打印格式要根据ElemType调整
    }
    printf("\n\n");
}

// 释放动态顺序表的内存
void DestroyDynamicList(DynamicSqlList *L) {
    if (L->Data != NULL) {
        free(L->Data);      // 释放动态分配的内存
        L->Data = NULL;     // 避免悬空指针
        L->MaxSize = 0;
        L->length = 0;
        printf("动态顺序表内存已释放\n");
    }
}

// ========== 主函数演示 ==========
int main() {
    printf("========== 顺序表：静态分配 vs 动态分配 演示 ==========\n\n");
    
    // 1. 创建并初始化两种顺序表
    StaticSqlList staticList;           // 静态分配，内存在栈上
    DynamicSqlList dynamicList;         // 动态分配，内存在堆上
    
    InitStaticList(&staticList);        // 初始化静态表
    InitDynamicList(&dynamicList, 3);   // 初始化动态表，初始容量为3
    
    // 2. 测试插入少量数据
    printf("========== 测试插入少量数据 ==========\n");
    InsertStaticList(&staticList, 0, 10);
    InsertStaticList(&staticList, 1, 20);
    InsertStaticList(&staticList, 2, 30);
    
    InsertDynamicList(&dynamicList, 0, 100);
    InsertDynamicList(&dynamicList, 1, 200);
    InsertDynamicList(&dynamicList, 2, 300);
    
    printf("\n");
    PrintStaticList(&staticList);
    PrintDynamicList(&dynamicList);
    
    // 3. 测试容量限制
    printf("========== 测试容量扩展 ==========\n");
    printf("尝试向动态表插入第4个元素（超出初始容量3）：\n");
    InsertDynamicList(&dynamicList, 3, 400);  // 这会触发动态扩展
    
    printf("尝试向动态表继续插入：\n");
    InsertDynamicList(&dynamicList, 4, 500);
    InsertDynamicList(&dynamicList, 5, 600);
    
    printf("\n");
    PrintDynamicList(&dynamicList);
    
    // 4. 演示静态表的容量限制
    printf("========== 演示静态表容量限制 ==========\n");
    printf("向静态表插入更多数据，测试容量限制...\n");
    for (int i = 3; i < 12; i++) {  // 尝试插入到第12个位置
        InsertStaticList(&staticList, i, (i+1)*10);
    }
    
    printf("\n");
    PrintStaticList(&staticList);
    
    // 5. 清理内存
    printf("========== 内存管理 ==========\n");
    DestroyDynamicList(&dynamicList);  // 动态表需要手动释放内存
    printf("静态表会在函数结束时自动释放（在栈上）\n");
    
    printf("\n========== 总结对比 ==========\n");
    printf("静态分配：\n");
    printf("  优点：简单，不需要手动管理内存，访问速度快\n");
    printf("  缺点：容量固定，可能浪费内存或容量不够\n\n");
    printf("动态分配：\n");
    printf("  优点：容量灵活，可以根据需要调整\n");
    printf("  缺点：需要手动管理内存，有内存泄漏风险\n");
    
    return 0;
}

/*
ElemType 的优势：

1. 类型抽象：
   - 只需要修改 typedef int ElemType; 这一行
   - 就可以将整个顺序表改为存储其他类型的数据
   - 比如：typedef char ElemType; 或 typedef float ElemType;

2. 可维护性：
   - 代码更加规范，符合数据结构教材的标准写法
   - 如果要改变数据类型，只需要修改一处

3. 可读性：
   - 代码意图更加清晰，一看就知道这是元素类型
   - 便于其他程序员理解和维护

4. 扩展性：
   - 如果将来要支持自定义结构体作为元素，只需要修改ElemType定义
   - 例如：typedef struct Student ElemType;

注意事项：
- 如果改变ElemType的类型，记得同时修改printf的格式说明符
- int用%d，char用%c，float用%f，字符串用%s等
*/
